{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Teemo Attacking"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #simulation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #模拟"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findPoisonedDuration"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #提莫攻击"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>在《英雄联盟》的世界中，有一个叫 “提莫” 的英雄。他的攻击可以让敌方英雄艾希（编者注：寒冰射手）进入中毒状态。</p>\n",
    "\n",
    "<p>当提莫攻击艾希，艾希的中毒状态正好持续&nbsp;<code>duration</code> 秒。</p>\n",
    "\n",
    "<p>正式地讲，提莫在 <code>t</code> 发起攻击意味着艾希在时间区间 <code>[t, t + duration - 1]</code>（含 <code>t</code> 和 <code>t + duration - 1</code>）处于中毒状态。如果提莫在中毒影响结束 <strong>前</strong> 再次攻击，中毒状态计时器将会 <strong>重置</strong> ，在新的攻击之后，中毒影响将会在 <code>duration</code> 秒后结束。</p>\n",
    "\n",
    "<p>给你一个 <strong>非递减</strong> 的整数数组 <code>timeSeries</code> ，其中 <code>timeSeries[i]</code> 表示提莫在 <code>timeSeries[i]</code> 秒时对艾希发起攻击，以及一个表示中毒持续时间的整数 <code>duration</code> 。</p>\n",
    "\n",
    "<p>返回艾希处于中毒状态的 <strong>总</strong> 秒数。</p>\n",
    "&nbsp;\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>timeSeries = [1,4], duration = 2\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>提莫攻击对艾希的影响如下：\n",
    "- 第 1 秒，提莫攻击艾希并使其立即中毒。中毒状态会维持 2 秒，即第 1 秒和第 2 秒。\n",
    "- 第 4 秒，提莫再次攻击艾希，艾希中毒状态又持续 2 秒，即第 4 秒和第 5 秒。\n",
    "艾希在第 1、2、4、5 秒处于中毒状态，所以总中毒秒数是 4 。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>timeSeries = [1,2], duration = 2\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>提莫攻击对艾希的影响如下：\n",
    "- 第 1 秒，提莫攻击艾希并使其立即中毒。中毒状态会维持 2 秒，即第 1 秒和第 2 秒。\n",
    "- 第 2 秒，提莫再次攻击艾希，并重置中毒计时器，艾希中毒状态需要持续 2 秒，即第 2 秒和第 3 秒。\n",
    "艾希在第 1、2、3 秒处于中毒状态，所以总中毒秒数是 3 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= timeSeries.length &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>0 &lt;= timeSeries[i], duration &lt;= 10<sup>7</sup></code></li>\n",
    "\t<li><code>timeSeries</code> 按 <strong>非递减</strong> 顺序排列</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [teemo-attacking](https://leetcode.cn/problems/teemo-attacking/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [teemo-attacking](https://leetcode.cn/problems/teemo-attacking/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,4]\\n2', '[1,2]\\n2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPoisonedDuration(self, timeSeries: List[int], duration: int) -> int:\n",
    "        health,res = 0,0\n",
    "        for i in range(len(timeSeries)):\n",
    "            if timeSeries[i] >= health:\n",
    "                res += duration\n",
    "            else:\n",
    "                res += timeSeries[i] + duration - health\n",
    "            health = timeSeries[i] + duration\n",
    "        return res \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPoisonedDuration(self, timeSeries: List[int], duration: int) -> int:\n",
    "        res=[]\n",
    "        n1=len(timeSeries)\n",
    "        for i in range(n1):\n",
    "            l=[]\n",
    "            l.append(timeSeries[i])\n",
    "            l.append(timeSeries[i]+duration)\n",
    "            res.append(l)\n",
    "        count=0\n",
    "        i=0\n",
    "        while i<(n1-1):\n",
    "            if res[i][1]<res[i+1][0]:\n",
    "                count+=res[i+1][0]-res[i][1]\n",
    "            i+=1\n",
    "        return res[n1-1][1]-res[0][0]-count\n",
    "       \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPoisonedDuration(self, timeSeries: List[int], duration: int) -> int:\n",
    "        timeSeries.sort()\n",
    "        res = [[timeSeries[0], timeSeries[0] + duration]]  # 得到第一个的区间\n",
    "        result = duration\n",
    "\n",
    "        for index in range(1, len(timeSeries)):\n",
    "            start_time = timeSeries[index]\n",
    "            end_time = start_time + duration\n",
    "            if res[-1][0] <= start_time <= res[-1][1]:\n",
    "                result += duration - (res[-1][1] - start_time)  # 如果有区间重叠，那么加上重叠的差值\n",
    "                res[-1][1] = end_time\n",
    "            else:\n",
    "                res.append([start_time, end_time])\n",
    "                result += duration  # 如果没有重叠，那么直接加上即可\n",
    "        # result = 0   #这么算也行， 就是性能差了点， 先把区间数组给出了， 再去做加法也行\n",
    "        # for content in res:\n",
    "        #     result += content[1] - content[0]\n",
    "        # print(res, result)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPoisonedDuration(self, timeSeries: List[int], duration: int) -> int:\n",
    "        intervals = []\n",
    "        for i in timeSeries:\n",
    "\t        intervals.append([i, i+duration])\n",
    "        print(intervals)\n",
    "        intervals.sort(key=lambda x: x[0])\n",
    "        ans = []\n",
    "        for i in intervals:\n",
    "            if not ans or ans[-1][1] < i[0]:\n",
    "                ans.append(i)\n",
    "            else:\n",
    "                ans[-1][1] = max(ans[-1][1], i[1])\n",
    "        target = 0\n",
    "        for i in ans:\n",
    "            target+=i[1]-i[0]\n",
    "        return target"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPoisonedDuration(self, timeSeries: List[int], duration: int) -> int:\n",
    "        return timeSeries[-1] + duration - timeSeries[0] - sum([max(timeSeries[i] - timeSeries[i - 1] - duration, 0) for i in range(1, len(timeSeries))])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPoisonedDuration(self, timeSeries: List[int], duration: int) -> int:\n",
    "        intv = []\n",
    "        for i in range(len(timeSeries)):\n",
    "            intv.append([timeSeries[i], timeSeries[i] + duration - 1])\n",
    "        \n",
    "        # merge intervals\n",
    "        res = 0\n",
    "        left, right = intv[0][0], intv[0][1]\n",
    "        for i in range(1, len(intv)):\n",
    "            if intv[i][0] <= right and intv[i][1] >= left:\n",
    "                left = min(left, intv[i][0])\n",
    "                right = max(right, intv[i][1])\n",
    "            else:\n",
    "                res += right - left + 1\n",
    "                left, right = intv[i][0], intv[i][1]\n",
    "        res += right - left + 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPoisonedDuration(self, timeSeries: List[int], duration: int) -> int:\n",
    "        timeSeries = [timeSeries[0], *timeSeries]\n",
    "        return len(timeSeries) * duration - sum([max(timeSeries[i] + duration - timeSeries[i+1], 0) for i in range(len(timeSeries)-1)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPoisonedDuration(self, timeSeries: List[int], duration: int) -> int:\n",
    "        res=0\n",
    "        for i in range(1,len(timeSeries)):\n",
    "            res+=min(timeSeries[i] - timeSeries[i-1],duration)\n",
    "        res+=duration\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPoisonedDuration(self, timeSeries: List[int], duration: int) -> int:\n",
    "        ans, expired = 0, 0\n",
    "        for i in range(len(timeSeries)):\n",
    "            if timeSeries[i] >= expired:\n",
    "                ans += duration\n",
    "            else:\n",
    "                ans += timeSeries[i] + duration - expired\n",
    "            expired = timeSeries[i] + duration\n",
    "            \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def findPoisonedDuration(self, timeSeries: List[int], duration: int) -> int:\r\n",
    "        l = len(timeSeries)\r\n",
    "        tmp = [((timeSeries[i+1]-timeSeries[i]) if (timeSeries[i+1]-timeSeries[i])<=duration else duration) for i in range(l-1)] + [duration]\r\n",
    "        return sum(tmp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPoisonedDuration(self, timeSeries: List[int], duration: int) -> int:\n",
    "        n = len(timeSeries)\n",
    "        if n == 1:\n",
    "            return duration\n",
    "            \n",
    "        res = duration\n",
    "\n",
    "        for i in range(n-1):\n",
    "            if timeSeries[i+1] - timeSeries[i] > duration:\n",
    "                res += duration\n",
    "            else:\n",
    "                res += timeSeries[i+1] - timeSeries[i]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPoisonedDuration(self, timeSeries: List[int], duration: int) -> int:\n",
    "        cnt=0\n",
    "\n",
    "        for i in range(1,len(timeSeries)):\n",
    "            cnt+=min(duration,timeSeries[i]-timeSeries[i-1])\n",
    "        return cnt+duration\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPoisonedDuration(self, timeSeries: List[int], duration: int) -> int:\n",
    "        timeSeries = [timeSeries[0], *timeSeries]\n",
    "        return len(timeSeries) * duration - sum([max(timeSeries[i] + duration - timeSeries[i+1], 0) for i in range(len(timeSeries)-1)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPoisonedDuration(self, timeSeries: List[int], duration: int) -> int:\n",
    "        ans = 0\n",
    "        for i in range(len(timeSeries)):\n",
    "            cur_t = timeSeries[i]\n",
    "            next_t = timeSeries[i+1] if i < len(timeSeries) - 1 else 1e7\n",
    "            ans += min(next_t - cur_t, duration)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPoisonedDuration(self, timeSeries: List[int], duration: int) -> int:\n",
    "        res = duration\n",
    "        n = len(timeSeries)\n",
    "        for i in range(n):\n",
    "            if i == 0 :continue\n",
    "            res += duration if timeSeries[i]-timeSeries[i-1]>duration else timeSeries[i]-timeSeries[i-1]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPoisonedDuration(self, timeSeries: List[int], duration: int) -> int:\n",
    "        re = 0\n",
    "        for i in range(1,len(timeSeries)):\n",
    "            dif = timeSeries[i] - timeSeries[i-1]\n",
    "            if dif < duration:\n",
    "                re += dif\n",
    "            else:\n",
    "                re += duration\n",
    "\n",
    "        re += duration\n",
    "        return re"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPoisonedDuration(self, timeSeries: List[int], duration: int) -> int:\n",
    "        end = timeSeries[0]\n",
    "        ans = 0\n",
    "        for t in timeSeries:\n",
    "            if t >= end:\n",
    "                ans += duration\n",
    "            else:\n",
    "                ans += t + duration - end\n",
    "            end = t + duration\n",
    "\n",
    "        return ans\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPoisonedDuration(self, timeSeries: List[int], duration: int) -> int:\n",
    "        timeSeries = [timeSeries[0], *timeSeries]\n",
    "        return len(timeSeries) * duration - sum([max(timeSeries[i] + duration - timeSeries[i+1], 0) for i in range(len(timeSeries)-1)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPoisonedDuration(self, timeSeries: List[int], duration: int) -> int:\n",
    "        timeSeries.sort()\n",
    "        endT = 0\n",
    "        allT = 0\n",
    "        for x in timeSeries:\n",
    "            if endT > x:\n",
    "                allT -= (endT - x)\n",
    "                endT = x + duration\n",
    "                allT += duration\n",
    "            else:\n",
    "                endT = x + duration\n",
    "                allT += duration\n",
    "        return allT"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPoisonedDuration(self, timeSeries: List[int], duration: int) -> int:\n",
    "        # count = 0\n",
    "        # for i in range(len(timeSeries) - 1):\n",
    "        #     count += min(duration, timeSeries[i + 1] - timeSeries[i])\n",
    "        # return count + duration\n",
    "\n",
    "        count = len(timeSeries) * duration\n",
    "        for i in range(len(timeSeries) - 1):\n",
    "            if duration > timeSeries[i + 1] - timeSeries[i]:\n",
    "                count -= duration - timeSeries[i + 1] + timeSeries[i]\n",
    "        return count\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPoisonedDuration(self, timeSeries: List[int], duration: int) -> int:\n",
    "        a=0\n",
    "        for i in range(len(timeSeries)):\n",
    "            if i==0:\n",
    "                a+=duration\n",
    "            elif timeSeries[i]>(timeSeries[i-1]+duration):\n",
    "                a+=duration\n",
    "            else:\n",
    "                a=a+timeSeries[i]-timeSeries[i-1]\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPoisonedDuration(self, timeSeries: List[int], duration: int) -> int:\n",
    "        count = 0\n",
    "        for i in range(len(timeSeries) - 1):\n",
    "            count += min(duration, timeSeries[i + 1] - timeSeries[i])\n",
    "        return count + duration\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPoisonedDuration(self, timeSeries: List[int], duration: int) -> int:\n",
    "        durs = [(s,s+duration-1) for s in timeSeries]\n",
    "        if not durs: return 0\n",
    "        res = []\n",
    "        start, end = durs[0]\n",
    "        for i in range(1,len(durs)):\n",
    "            if durs[i][0] <= end:\n",
    "                end = durs[i][1]\n",
    "            else:\n",
    "                res.append((start,end))\n",
    "                start,end = durs[i]\n",
    "        res.append((start,end))\n",
    "        return sum(map(lambda x: x[1]-x[0]+1,res))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPoisonedDuration(self, timeSeries: List[int], duration: int) -> int:\n",
    "        durt=0\n",
    "        for i in range(len(timeSeries)-1):\n",
    "            t=timeSeries[i+1]-timeSeries[i]\n",
    "            if t<duration:\n",
    "                durt+=t\n",
    "            else:\n",
    "                durt+=duration\n",
    "        return durt + duration"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPoisonedDuration(self, timeSeries: List[int], duration: int) -> int:\n",
    "        # res = 0\n",
    "        # t0 = 0\n",
    "        # for time in timeSeries:\n",
    "        #     if t0 <= time:\n",
    "        #         res += duration\n",
    "        #         t0 = time + duration\n",
    "        #     else:\n",
    "        #         tmp = 0 if t0 - time > duration else duration+time - t0\n",
    "        #         res += tmp \n",
    "        #         t0 += tmp\n",
    "        # return res\n",
    "        if not timeSeries:\n",
    "            return 0\n",
    "\n",
    "        total_duration = 0\n",
    "        for i in range(len(timeSeries)-1):\n",
    "            total_duration += min(timeSeries[i+1]-timeSeries[i], duration)\n",
    "        \n",
    "        total_duration += duration\n",
    "\n",
    "        return total_duration"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPoisonedDuration(self, timeSeries: List[int], duration: int) -> int:\n",
    "        # total_sec = []\n",
    "        # for i in timeSeries:\n",
    "        #     for j in range(duration):\n",
    "        #         total_sec.append(i+j)\n",
    "        # return len(set(total_sec))\n",
    "\n",
    "        # frozen_count = 0\n",
    "        # for count, i in enumerate(timeSeries):\n",
    "        #     cur_end = i + duration - 1\n",
    "        #     if count < len(timeSeries)-1:\n",
    "        #         if timeSeries[count+1] <= cur_end:\n",
    "        #             cancel = timeSeries[count+1]-cur_end+1\n",
    "        #             frozen_count += duration*2 - cancel\n",
    "        #         else:\n",
    "        #             frozen_count += duration*2\n",
    "        # return frozen_count\n",
    "        res = 0\n",
    "        for i in range(len(timeSeries)-1):\n",
    "            if timeSeries[i] + duration - 1 < timeSeries[i+1]:\n",
    "                res +=  duration\n",
    "            else:\n",
    "                res += duration - (timeSeries[i]+duration-timeSeries[i+1])\n",
    "        return res + duration\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPoisonedDuration(self, timeSeries: List[int], duration: int) -> int:\n",
    "        n = len(timeSeries)\n",
    "        \n",
    "        result = 0\n",
    "        \n",
    "        for i in range(n - 1):\n",
    "            if timeSeries[i] <= timeSeries[i + 1] <= timeSeries[i] + duration:\n",
    "                result += timeSeries[i + 1] - timeSeries[i]\n",
    "            else:\n",
    "                result += duration\n",
    "        result += duration\n",
    "        \n",
    "        return result\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPoisonedDuration(self, timeSeries: List[int], duration: int) -> int:\n",
    "        res = 0\n",
    "        if len(timeSeries) == 1:\n",
    "            return duration\n",
    "        for i in range(1, len(timeSeries)):\n",
    "            if timeSeries[i] - timeSeries[i-1] >= duration:\n",
    "                res += duration\n",
    "            else:\n",
    "                res += timeSeries[i] - timeSeries[i-1]\n",
    "        return res + duration"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPoisonedDuration(self, timeSeries: List[int], duration: int) -> int:\n",
    "        ans = 0\n",
    "        for t, t1 in pairwise(timeSeries):\n",
    "            if t1 - t < duration:\n",
    "                ans += t1 - t\n",
    "            else:\n",
    "                ans += duration\n",
    "        return ans + duration"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPoisonedDuration(self, timeSeries: List[int], duration: int) -> int:\n",
    "        result=duration\n",
    "        for i in range(len(timeSeries)-1):\n",
    "            if timeSeries[i+1]-timeSeries[i]>=duration:\n",
    "                result+=duration\n",
    "            else:\n",
    "                result+=timeSeries[i+1]-timeSeries[i] \n",
    "        return result            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPoisonedDuration(self, timeSeries: List[int], duration: int) -> int:\n",
    "        res = 0\n",
    "        for i in range(len(timeSeries)-1):\n",
    "            if timeSeries[i] + (duration-1) < timeSeries[i+1]:\n",
    "                res += duration\n",
    "            else:\n",
    "                res += duration - ((timeSeries[i]+duration)-timeSeries[i+1])\n",
    "        res += duration\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPoisonedDuration(self, timeSeries: List[int], duration: int) -> int:\n",
    "        n = len(timeSeries)\n",
    "        timeSeries+=[10**10]\n",
    "        ans = 0\n",
    "        flag = 0\n",
    "        for i in range(n):\n",
    "            if flag==0:\n",
    "                start = timeSeries[i]\n",
    "            end = timeSeries[i]+duration-1\n",
    "            if end<timeSeries[i+1]:\n",
    "                flag = 0\n",
    "                ans+=end-start+1\n",
    "            else:\n",
    "                flag = 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPoisonedDuration(self, timeSeries: List[int], duration: int) -> int:\n",
    "        res = 0\n",
    "        for i, num in enumerate(timeSeries):\n",
    "            if i == 0:\n",
    "                res = duration\n",
    "            elif duration > num - timeSeries[i-1]:\n",
    "                res = res + num - timeSeries[i-1]\n",
    "            else:\n",
    "                res += duration\n",
    "        return res\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPoisonedDuration(self, timeSeries: List[int], duration: int) -> int:\n",
    "        res = duration\n",
    "        length = len(timeSeries)\n",
    "        if length == 1:\n",
    "            return res\n",
    "        for i in range(len(timeSeries) - 1):\n",
    "            res += min(duration,timeSeries[i+1]-timeSeries[i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPoisonedDuration(self, timeSeries: List[int], duration: int) -> int:\n",
    "        res = 0\n",
    "        last = -1\n",
    "        for i in timeSeries:\n",
    "            if last < i:\n",
    "                res += duration\n",
    "            if last >= i:\n",
    "                res += i + duration - 1 - last\n",
    "            last = i + duration - 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPoisonedDuration(self, timeSeries: List[int], duration: int) -> int:\n",
    "        t= duration\n",
    "        for i in range(len(timeSeries)-1):\n",
    "            if timeSeries[i]+duration > timeSeries[i+1]:\n",
    "                t += timeSeries[i+1]-timeSeries[i]\n",
    "            else:\n",
    "                t += duration\n",
    "        return t\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPoisonedDuration(self, timeSeries: List[int], duration: int) -> int:\n",
    "        return sum(min(timeSeries[i+1], timeSeries[i] + duration) - timeSeries[i] for i in range(len(timeSeries) - 1)) + duration\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPoisonedDuration(self, timeSeries: List[int], duration: int) -> int:\n",
    "        count=0\n",
    "        for i in range(1,len(timeSeries)):\n",
    "            if timeSeries[i]-timeSeries[i-1]<duration:\n",
    "                count+= timeSeries[i]-timeSeries[i-1]\n",
    "            else:\n",
    "                count+=duration\n",
    "        return count+duration\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPoisonedDuration(self, timeSeries: List[int], duration: int) -> int:\n",
    "        res = 0\n",
    "        start = -1\n",
    "        for x in timeSeries:\n",
    "            if start < 0:\n",
    "                start = x\n",
    "            else:\n",
    "                res += min(x - start, duration)\n",
    "                start = x\n",
    "        return res + duration"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPoisonedDuration(self, timeSeries: List[int], duration: int) -> int:\n",
    "        end = ans =0\n",
    "        for x in timeSeries:\n",
    "            ans += duration\n",
    "            if x < end:\n",
    "                ans -= end - x\n",
    "            end = x + duration\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPoisonedDuration(self, timeSeries: List[int], duration: int) -> int:\n",
    "        time = duration\n",
    "        for i in range(1, len(timeSeries)):\n",
    "            if timeSeries[i] - timeSeries[i - 1] < duration:\n",
    "                ex = timeSeries[i] - timeSeries[i - 1]\n",
    "                if ex > 0:\n",
    "                    time += ex\n",
    "            else:\n",
    "                time += duration\n",
    "        return time\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPoisonedDuration(self, timeSeries: List[int], duration: int) -> int:\n",
    "        ans=0\n",
    "        n=len(timeSeries)\n",
    "        i=0\n",
    "        while i<n:\n",
    "            if i<n-1 and timeSeries[i]+duration-1>=timeSeries[i+1]:\n",
    "                ans+=timeSeries[i+1]-timeSeries[i]\n",
    "            else:\n",
    "                ans+=duration\n",
    "            i+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPoisonedDuration(self, timeSeries: List[int], duration: int) -> int:\n",
    "        cnt=0\n",
    "\n",
    "        for i in range(1,len(timeSeries)):\n",
    "            cnt+=min(duration,timeSeries[i]-timeSeries[i-1])\n",
    "        return cnt+duration"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPoisonedDuration(self, timeSeries: List[int], duration: int) -> int:\n",
    "        ans, expired = 0, 0\n",
    "        for i in range(len(timeSeries)):\n",
    "            if timeSeries[i] >= expired:\n",
    "                ans += duration\n",
    "            else:\n",
    "                ans += timeSeries[i] + duration - expired\n",
    "            expired = timeSeries[i] + duration\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPoisonedDuration(self, timeSeries: List[int], duration: int) -> int:\n",
    "        \n",
    "        \n",
    "        ans = 0\n",
    "        start = timeSeries[0]   # 中毒开始时间\n",
    "        end = start+duration     # 中毒结束时间\n",
    "\n",
    "        for i in range(0, len(timeSeries)):                 \n",
    "            if timeSeries[i]>end:           # 不在中毒状态发起攻击对前面中毒时间求和\n",
    "                ans += end -start       # 计算时间\n",
    "                start = timeSeries[i]      # 中毒开始时间\n",
    "                end = start+duration      \n",
    "            else:                           #在中毒状态发起攻击\n",
    "                end = timeSeries[i]+duration\n",
    "        ans += end-start            # 最后一次只是更新了开始时间，结束时间和对之前求和\n",
    "     \n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPoisonedDuration(self, timeSeries: List[int], duration: int) -> int:\n",
    "        res = duration # timeSeries[0] 对答案的贡献\n",
    "        for a, b in pairwise(timeSeries):\n",
    "            res += min(duration, b - a) # 累加b对答案的剩余贡献\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def findPoisonedDuration(self, timeSeries: List[int], duration: int) -> int:\r\n",
    "        total = 0\r\n",
    "        for i in range(len(timeSeries) - 1):\r\n",
    "            if timeSeries[i] + duration - 1 < timeSeries[i+1]:\r\n",
    "                total += duration\r\n",
    "            else:\r\n",
    "                total += timeSeries[i+1] - timeSeries[i]\r\n",
    "\r\n",
    "        return total + duration"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPoisonedDuration(self, timeSeries: List[int], duration: int) -> int:\n",
    "        cnt=0\n",
    "        start=timeSeries[0]\n",
    "        for i in timeSeries[1:]:\n",
    "            if duration+start<=i:\n",
    "                cnt+=duration\n",
    "            else:\n",
    "                cnt+=i-start\n",
    "            start=i\n",
    "        return cnt+duration\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPoisonedDuration(self, timeSeries: List[int], duration: int) -> int:\n",
    "        total_t = 0\n",
    "        n = len(timeSeries)\n",
    "        for i in range(n):\n",
    "            next_v = timeSeries[i] + duration\n",
    "            if i + 1 == n:\n",
    "                total_t += duration\n",
    "            elif next_v <= timeSeries[i+1]:\n",
    "                total_t += duration\n",
    "            else:\n",
    "                total_t += timeSeries[i+1] - timeSeries[i]\n",
    "        return total_t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPoisonedDuration(self, timeSeries: List[int], duration: int) -> int:\n",
    "        timeall=0\n",
    "        for i in range(0,len(timeSeries)-1):\n",
    "            if timeSeries[i]+duration<=timeSeries[i+1]:\n",
    "                timeall+=duration\n",
    "            else:\n",
    "                timeall=timeall+timeSeries[i+1]-timeSeries[i]        \n",
    "        return timeall+duration\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPoisonedDuration(self, timeSeries: List[int], duration: int) -> int:\n",
    "        ans = 0\n",
    "        for i in range(len(timeSeries)-1):\n",
    "            if timeSeries[i+1] - timeSeries[i] < duration:\n",
    "                ans += timeSeries[i+1] - timeSeries[i]\n",
    "            else:\n",
    "                ans += duration\n",
    "        ans += duration\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPoisonedDuration(self, timeSeries: List[int], duration: int) -> int:\n",
    "        ans = duration\n",
    "        timeSeries = collections.deque(timeSeries)\n",
    "        for i in range(1, len(timeSeries)):\n",
    "            if (timeSeries[i] - timeSeries[i - 1]) >= duration:\n",
    "                ans += duration\n",
    "            else:\n",
    "                ans += timeSeries[i] - timeSeries[i - 1]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPoisonedDuration(self, timeSeries: List[int], duration: int) -> int:\n",
    "        ans, expired = 0, 0\n",
    "        for i in range(len(timeSeries)):\n",
    "            if timeSeries[i] >= expired:\n",
    "                ans += duration\n",
    "            else:\n",
    "                ans += timeSeries[i] + duration - expired\n",
    "            expired = timeSeries[i] + duration\n",
    "        return ans\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPoisonedDuration(self, timeSeries: List[int], duration: int) -> int:\n",
    "        x=0\n",
    "        for i in range(len(timeSeries)):\n",
    "            if i==0:\n",
    "                x+=duration\n",
    "            elif timeSeries[i]-timeSeries[i-1]<duration:\n",
    "                x+=(timeSeries[i]-timeSeries[i-1])\n",
    "            else:\n",
    "                x+=duration\n",
    "        return x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPoisonedDuration(self, timeSeries: List[int], duration: int) -> int:\n",
    "        cnt = 0\n",
    "        start = timeSeries[0]\n",
    "        for i in timeSeries[1:]:\n",
    "            if i - start>=duration:\n",
    "                cnt+=duration\n",
    "            else:\n",
    "                cnt = i+cnt-start\n",
    "            start = i\n",
    "        return cnt+duration"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPoisonedDuration(self, timeSeries: List[int], duration: int) -> int:\n",
    "        res =0\n",
    "        start = timeSeries[0]\n",
    "        n = len(timeSeries)\n",
    "        for i in range(1,n):\n",
    "            if start+duration-1 < timeSeries[i]:\n",
    "                res += duration\n",
    "                start = timeSeries[i]\n",
    "            else:\n",
    "                res += timeSeries[i]-start\n",
    "                start = timeSeries[i]\n",
    "        res += duration\n",
    "        return res\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPoisonedDuration(self, timeSeries: List[int], duration: int) -> int:\n",
    "        end = ans = 0\n",
    "        for x in timeSeries:\n",
    "            ans += duration\n",
    "            if x < end:\n",
    "                ans -= end - x\n",
    "            end = x + duration\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPoisonedDuration(self, timeSeries: List[int], duration: int) -> int:\n",
    "        count = 0\n",
    "        for i in range(0, len(timeSeries) - 1):\n",
    "            if timeSeries[i] + duration <= timeSeries[i+1]:\n",
    "                count += duration\n",
    "            else:\n",
    "                count += timeSeries[i+1] - timeSeries[i]\n",
    "        count += duration\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPoisonedDuration(self, timeSeries: List[int], duration: int) -> int:\n",
    "        n = len(timeSeries)\n",
    "        res = 0\n",
    "        for i in range(1,n):\n",
    "            temp = timeSeries[i]-timeSeries[i-1]\n",
    "            if temp>= duration:\n",
    "                res+=duration\n",
    "            else:\n",
    "                res+=temp\n",
    "        res +=duration\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPoisonedDuration(self, timeSeries: List[int], duration: int) -> int:\n",
    "        sum = 0\n",
    "        for i in range(0,len(timeSeries)-1):\n",
    "            if timeSeries[i+1] - timeSeries[i] >= duration:\n",
    "                sum += duration\n",
    "            else:\n",
    "                sum += timeSeries[i+1] - timeSeries[i]\n",
    "        return sum + duration"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def findPoisonedDuration(self, timeSeries: List[int], duration: int) -> int:\r\n",
    "        n = len(timeSeries)\r\n",
    "        res = 0 \r\n",
    "        for i in range(1,n):\r\n",
    "            if timeSeries[i-1] + duration - 1 < timeSeries[i]:\r\n",
    "                res += duration\r\n",
    "            else:\r\n",
    "                res += timeSeries[i] - timeSeries[i - 1]\r\n",
    "        return res+duration"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "[1,4]\n",
    "2\n",
    "[1,2]\n",
    "2\n",
    "\n",
    "1 <= timeSeries.length <= 1e4\n",
    "0 <= timeSeries[i], duration <= 1e7\n",
    "timeSeries is sorted in non-decreasing order.\n",
    "\n",
    "Array,Simulation\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def findPoisonedDuration(self, timeSeries: List[int], duration: int) -> int:\n",
    "        res = 0\n",
    "        for i in range(1, len(timeSeries)):\n",
    "            res += min(timeSeries[i]-timeSeries[i-1], duration)\n",
    "        return res+duration"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def findPoisonedDuration(self, timeSeries, duration):\n",
    "        ans = duration\n",
    "        for i in range(1, len(timeSeries)):\n",
    "            ans += min(timeSeries[i] - timeSeries[i - 1], duration)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPoisonedDuration(self, timeSeries: List[int], duration: int) -> int:\n",
    "        res=0\n",
    "        for i in range(len(timeSeries)):\n",
    "            if i==len(timeSeries)-1:\n",
    "                res+=duration\n",
    "            else:\n",
    "                if timeSeries[i]+duration-1>=timeSeries[i+1]:\n",
    "                    res+=timeSeries[i+1]-timeSeries[i]\n",
    "                else:\n",
    "                    res+=duration\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPoisonedDuration(self, timeSeries: List[int], duration: int) -> int:\n",
    "        ans = 0\n",
    "        for j in range(1, len(timeSeries)):\n",
    "            if timeSeries[j] - timeSeries[j - 1] >= duration:\n",
    "                ans += duration\n",
    "            else:\n",
    "                ans += timeSeries[j] - timeSeries[j - 1]\n",
    "        return ans + duration"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findPoisonedDuration(self, timeSeries: List[int], duration: int) -> int:\n",
    "        '''\n",
    "\n",
    "        for i in [0, -2]\n",
    "            s[i+1] - s[i] >= duration time+=duration\n",
    "            else:time+=s[i+1] - s[i]-1\n",
    "\n",
    "        :param timeSeries:\n",
    "        :param duration:\n",
    "        :return:\n",
    "        '''\n",
    "        count = 0\n",
    "        if duration == 0:return 0\n",
    "        l = len(timeSeries)\n",
    "        for i in range(l - 1):\n",
    "\n",
    "            if timeSeries[i+1] - timeSeries[i] >= duration:\n",
    "                count += duration\n",
    "            else:\n",
    "                count += timeSeries[i+1] - timeSeries[i]\n",
    "\n",
    "        # if timeSeries[i-1] - timeSeries[i-2] >= duration:\n",
    "        #     count += duration\n",
    "        # else:\n",
    "        #     count += timeSeries[i+1] - timeSeries[i] - 1\n",
    "        count += duration\n",
    "        return count\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    timeSeries = [1, 4]\n",
    "    duration = 2\n",
    "    print(Solution().findPoisonedDuration(timeSeries, duration))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPoisonedDuration(self, timeSeries: List[int], duration: int) -> int:\n",
    "        if len(timeSeries) == 1:\n",
    "            return duration\n",
    "        total = 0\n",
    "        i = 0\n",
    "        while i < len(timeSeries)-1:\n",
    "            if timeSeries[i+1]-timeSeries[i] > duration:\n",
    "                total += duration\n",
    "            else:\n",
    "                total += timeSeries[i+1]-timeSeries[i]\n",
    "            i += 1\n",
    "        total += duration\n",
    "        return total\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPoisonedDuration(self, timeSeries: List[int], duration: int) -> int:\n",
    "        time = 0\n",
    "        for i in range(1, len(timeSeries)):\n",
    "            if timeSeries[i] - timeSeries[i-1] <= duration:\n",
    "                time = time + timeSeries[i] - timeSeries[i-1]\n",
    "            else:\n",
    "                time = time + duration\n",
    "        time = time + duration\n",
    "        return time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPoisonedDuration(self, timeSeries: List[int], duration: int) -> int:\n",
    "        sum = duration\n",
    "        for i in range(len(timeSeries)-1):\n",
    "            time = timeSeries[i + 1] - timeSeries[i]\n",
    "            sum +=  duration if duration <= time else time \n",
    "        return sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPoisonedDuration(self, timeSeries: List[int], duration: int) -> int:\n",
    " \n",
    "        result = duration\n",
    "        for i in range(1, len(timeSeries)):\n",
    "            if timeSeries[i] <= timeSeries[i - 1] + duration - 1:\n",
    "                result += timeSeries[i] - timeSeries[i - 1]\n",
    "            else:\n",
    "                result += duration\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPoisonedDuration(self, timeSeries: List[int], duration: int) -> int:\n",
    "        if timeSeries==[]:\n",
    "            return 0\n",
    "        answer=0\n",
    "        timeSeries.append(-1)\n",
    "        slow=0;fast=1\n",
    "        while timeSeries[fast]!=-1:\n",
    "            if timeSeries[fast]<=timeSeries[slow]+duration:\n",
    "                answer+=timeSeries[fast]-timeSeries[slow]\n",
    "            else:\n",
    "                answer+=duration\n",
    "            fast+=1\n",
    "            slow+=1\n",
    "        answer+=duration\n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPoisonedDuration(self, timeSeries: List[int], duration: int) -> int:\n",
    "        if len(timeSeries)==0:\n",
    "            return 0\n",
    "        count = 0\n",
    "        for i in range(1,len(timeSeries)):\n",
    "            if timeSeries[i-1] + duration > timeSeries[i]:\n",
    "                count += timeSeries[i] - timeSeries[i-1]\n",
    "            else:\n",
    "                count += duration\n",
    "        count += duration\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPoisonedDuration(self, timeSeries: List[int], duration: int) -> int:\n",
    "       answer=0\n",
    "       n=len(timeSeries)\n",
    "       for i in range(n-1):\n",
    "           if timeSeries[i] + duration <= timeSeries[i+1]:\n",
    "               answer+=duration\n",
    "           else:answer+=timeSeries[i+1]-timeSeries[i]\n",
    "       return answer+duration\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
